package JZ_Offer.dataStructure.list;

import base.ListNode;

/**
 * 合并两个排序的链表
 * <p>
 * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * 数据范围： 0 \le n \le 10000≤n≤1000，-1000 \le 节点值 \le 1000−1000≤节点值≤1000
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 * <p>
 * 如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
 *
 * @Author piper
 * @Date 2019/12/5 12:40 下午
 */
public class JZ25_合并两个排序的链表 {

    private static ListNode Merge(ListNode list1, ListNode list2) {
        ListNode head = null, tail = null;
        while (list1 != null && list2 != null) {
            if (list2.val < list1.val) {
                if (tail == null) {
                    head = list2;
                } else {
                    tail.next = list2;
                }
                tail = list2;
                list2 = list2.next;
            } else {
                if (tail == null) {
                    head = list1;
                } else {
                    tail.next = list1;
                }
                tail = list1;
                list1 = list1.next;
            }
        }

        ListNode cur = list1 != null ? list1 : list2 != null ? list2 : null;
        if (cur != null) {
            if (tail == null) {
                head = cur;
            } else {
                tail.next = cur;
            }
        }

        return head;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        System.out.println(Merge(a, b));
    }

}
